package seqlist.link.leetcode;

/**
 * @author yuisama
 * @date 2023/03/19 10:55
 * 判断是否是回文链表
 **/
public class Num234_IsPalindromeList {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        ListNode middleNode = middleNode(head);
        // 将中间节点之后的子链表进行反转
        ListNode l2 = reverseList(middleNode);
        while (head != null && l2 != null) {
            // 找反例
            if (head.val != l2.val) {
                return false;
            }
            head = head.next;
            l2 = l2.next;
        }
        return true;
    }
    // 找中间节点
    public ListNode middleNode(ListNode head) {
        // 快慢指针法
        ListNode low = head,fast = head;
        while (fast != null && fast.next != null) {
            low = low.next;
            fast = fast.next.next;
        }
        return low;
    }
    // 反转链表
    public ListNode reverseList(ListNode head) {
        // 1.base case
        if(head == null || head.next == null) {
            return head;
        }
        ListNode next = head.next;
        ListNode newHead = reverseList(head.next);
        // 拼接当前头结点和转后的子链表
        head.next = null;
        next.next = head;
        return newHead;
    }
}